package com.game.battle.common.map;

import java.util.LinkedList;
import java.util.PriorityQueue;

public class AStar {
	private OpenCloseMap m_ClosedSet;
	private OpenCloseMap m_OpenSet;
	private PriorityQueue<PathNode> m_OrderedOpenSet;
	private PathNode[][] m_CameFrom;
	private OpenCloseMap m_RuntimeGrid;
	public PathNode[][] m_SearchSpace;
	
	public int width;
	public int height;
	
	public AStar(int width,int height,Grid[][] grids){
		this.width = width;
		this.height = height;
		m_ClosedSet = new OpenCloseMap(width, height);
		m_OpenSet = new OpenCloseMap(width, height);
		m_SearchSpace = new PathNode[width][height];
		m_CameFrom = new PathNode[this.width][this.height];
		m_RuntimeGrid = new OpenCloseMap(this.width, this.height);
		m_OrderedOpenSet = new PriorityQueue<PathNode>();
		
		for(int h=0;h<width;h++){
			for(int w=0;w<height;w++){
				Grid grid = grids[h][w];
				
				m_SearchSpace[h][w] = new PathNode(grid.isWall, grid.pos, grid.x, grid.y);
			}
		}
	}
	
	
	/**
	 * @param inIgnoreObstacle
	 * @param inStartNode
	 * @param inEndNode
	 * @return
	 */
	public LinkedList<PathNode> search(boolean ignoreObstacle, int startX, int startY, int endX, int endY, float range)
	{
		PathNode startNode = m_SearchSpace[startX][startY];
		PathNode endNode = m_SearchSpace[endX][endY];
		boolean endNodeIsWall = false;
		LinkedList<PathNode> pathList = new LinkedList<>();
		if (startNode.getX() == endNode.getX() && startNode.getY() == endNode.getY()){
			pathList.add(startNode.userContext);
			return pathList;
		}
		//把目标点的障碍物属性置为false，即非障碍物，可以在最佳路径点内。不过没关系，目标点在最后总是要从最佳路径点中去除掉。
		if(endNode.getIsWall()) {
			endNodeIsWall = true;
			endNode.setIsWall(false);
		}
		//UP, DOWN, LEFT, RIGHT
		PathNode[] neighborNodes = new PathNode[8];
		//PathNode[] neighborNodes = new PathNode[8];
		
		m_ClosedSet.clear();
		m_OpenSet.clear();
		m_RuntimeGrid.clear();
		m_OrderedOpenSet.clear();
		
		for (int x = 0; x < this.width; x++)
		{
			for (int y = 0; y < this.height; y++)
			{
				m_CameFrom[x][y] = null;
			}
		}
		
		startNode.setgCost(0);
		startNode.sethCost(heuristic(startNode, endNode));
		startNode.setfCost(startNode.gethCost());
		
		m_OpenSet.add(startNode);
		m_OrderedOpenSet.offer(startNode);
		m_RuntimeGrid.add(startNode);

		//int nodes = 0;注释掉无效变量

		while (!m_OpenSet.isEmpty())
		{
			PathNode x = m_OrderedOpenSet.poll();	
			if (x.getX() == endNode.getX() && x.getY() == endNode.getY())
			{
				LinkedList<PathNode> result = reconstructPath(m_CameFrom, m_CameFrom[endNode.getX()][endNode.getY()]);
				if(endNodeIsWall==true) {
					//把目标点恢复为障碍物
					endNode.setIsWall(true);
				}
				else {
					//最后从最佳路径点中加入目标点。
					result.addLast(endNode.userContext);
				}
				return result;
			}
			
			m_OpenSet.remove(x);
			m_ClosedSet.add(x);
			
			storeNeighborNodes(x, neighborNodes);
			
			for (int i = 0; i < neighborNodes.length; i++)
			{
				PathNode y = neighborNodes[i];
				Boolean tentative_is_better;
				
				if (y == null) {
					continue;
				}
				if (y.userContext.getIsWall()) {
					//如果该点是障碍物
					if(ignoreObstacle) {
						//如果技能受障碍物影响，则该点肯定不能作为最佳路径上的点，所以continue。
						continue;
					}else {
						//如果该技能可以忽略障碍物，但是该点到目标点的直径距离大于攻击范围，则该点也不能作为最佳路径上的点，所以continue。
						if(heuristic(y, endNode) > range) {
							continue;
						}else{
						//如果该技能可以忽略障碍物，但是该点到目标点的直径距离小于等于攻击范围，则该点可以作为最佳路径上的点，所以继续执行后面的代码。
							if(heuristic(y, endNode) > range - 1.42f) {
								//如果该点正好处于攻击点上且又是障碍物，则该点不能作为最佳路径上点，因为人物不能站在障碍物上。
								continue;
							}
						}
					}
				}
				if (m_ClosedSet.contains(y)) {
					continue;
				}
				//nodes++;
				
				double tentative_g_score = m_RuntimeGrid.getNode(x).getgCost() + neighborDistance(x, y);
				Boolean wasAdded = false;
				
				if (!m_OpenSet.contains(y))
				{
					m_OpenSet.add(y);
					tentative_is_better = true;
					wasAdded = true;
				}
				else if (tentative_g_score < m_RuntimeGrid.getNode(y).getgCost())
				{
					tentative_is_better = true;
				}
				else
				{
					tentative_is_better = false;
				}
				
				if (tentative_is_better)
				{
					m_CameFrom[y.getX()][y.getY()] = x;
					
					if (!m_RuntimeGrid.contains(y)) {
						m_RuntimeGrid.add(y);
					}
					m_RuntimeGrid.getNode(y).setgCost(tentative_g_score);
					m_RuntimeGrid.getNode(y).sethCost(heuristic(y, endNode));
					m_RuntimeGrid.getNode(y).setfCost(m_RuntimeGrid.getNode(y).getgCost()+ m_RuntimeGrid.getNode(y).gethCost());
					
					if (wasAdded) {
						m_OrderedOpenSet.offer(y);
					}
//					else{
//						m_OrderedOpenSet.
//					}
				}
			}
		}
		//把目标点恢复为障碍物
		if(endNodeIsWall) {
			endNode.setIsWall(true);
		}
		return null;
	}
	private static Double SQRT_2 = Math.sqrt(2);
	private double neighborDistance(PathNode inStart, PathNode inEnd) {
		int diffX = Math.abs(inStart.getX() - inEnd.getX());
		int diffY = Math.abs(inStart.getY() - inEnd.getY());
		
		switch (diffX + diffY)
		{
		case 1: return 1;
		case 2: return SQRT_2;
		case 0: return 0;
		default :
			return 0;
		}
	}


	private void storeNeighborNodes(PathNode inAround, PathNode[] inNeighbors) {
		 int x = inAround.getX();
         int y = inAround.getY();

         if ((x > 0) && (y > 0))
             inNeighbors[0] = m_SearchSpace[x - 1][y - 1];
         else
             inNeighbors[0] = null;

         if (y > 0)
             inNeighbors[1] = m_SearchSpace[x][y - 1];
         else
             inNeighbors[1] = null;

         if ((x < this.width - 1) && (y > 0))
             inNeighbors[2] = m_SearchSpace[x + 1][ y - 1];
         else
             inNeighbors[2] = null;

         if (x > 0)
             inNeighbors[3] = m_SearchSpace[x - 1][y];
         else
             inNeighbors[3] = null;

         if (x < this.width - 1)
             inNeighbors[4] = m_SearchSpace[x + 1][ y];
         else
             inNeighbors[4] = null;

         if ((x > 0) && (y < this.height - 1))
             inNeighbors[5] = m_SearchSpace[x - 1][ y + 1];
         else
             inNeighbors[5] = null;

         if (y < this.height - 1)
             inNeighbors[6] = m_SearchSpace[x][y + 1];
         else
             inNeighbors[6] = null;

         if ((x < this.width - 1) && (y < this.height - 1))
             inNeighbors[7] = m_SearchSpace[x + 1][ y + 1];
         else
             inNeighbors[7] = null;

	}


	private LinkedList<PathNode> reconstructPath(PathNode[][] m_CameFrom,PathNode current_node) {
		LinkedList<PathNode> result = new LinkedList<PathNode>();
		
		reconstructPathRecursive(m_CameFrom, current_node, result);
		
		return result;
	}


	private void reconstructPathRecursive(PathNode[][] m_CameFrom,PathNode current_node, LinkedList<PathNode> result) {
		PathNode item = m_CameFrom[current_node.getX()][current_node.getY()];
		
		if (item != null)
		{
			reconstructPathRecursive(m_CameFrom, item, result);
			
			result.addLast(current_node.userContext);
		}
		else
			result.addLast(current_node.userContext);
	}


	private double heuristic(PathNode startNode, PathNode endNode) {
		return Math.sqrt((startNode.getX() - endNode.getX()) * (startNode.getX() - endNode.getX()) + (startNode.getY() - endNode.getY()) * (startNode.getY() - endNode.getY()));
	}

	private class OpenCloseMap
	{
		private PathNode[][] m_Map;
		public int width;
		public int height;
		public int count;
		
		public PathNode getNodeItemByIndex(int x, int y){
			return m_Map[x][y];
		}
		
		public PathNode getNode(PathNode node){
			return m_Map[node.getX()][node.getY()];
		}
		
		public boolean isEmpty(){
			return count == 0;
		}
		
		public OpenCloseMap(int inWidth, int inHeight)
		{
			m_Map = new PathNode[inWidth][inHeight];
			this.width = inWidth;
			this.height = inHeight;
		}
		
		public void add(PathNode inValue)
		{
			PathNode item = m_Map[inValue.getX()][inValue.getY()];
			this.count++;
			m_Map[inValue.getX()][inValue.getY()] = inValue;
		}
		
		public boolean contains(PathNode inValue)
		{
			PathNode item = m_Map[inValue.getX()][inValue.getY()];
			
			if (item == null)
				return false;
			
			return true;
		}
		
		public void remove(PathNode inValue)
		{
			PathNode item = m_Map[inValue.getX()][inValue.getY()];
			this.count--;
			m_Map[inValue.getX()][inValue.getY()] = null;
		}
		
		public void clear()
		{
			this.count = 0;
			
			for (int x = 0; x < this.width; x++)
			{
				for (int y = 0; y < this.height; y++)
				{
					m_Map[x][y] = null;
				}
			}
		}
	}
	
	/**
	 * 
	 * @param startX
	 * @param startY
	 * @param endX
	 * @param endY
	 */
	//该方法与前面的search方法合并为一个
//	public LinkedList<PathNode> search(boolean ignoreObstacle, int startX, int startY, int endX, int endY) {
//		PathNode startNode = m_SearchSpace[startX][startY];
//		PathNode endNode = m_SearchSpace[endX][endY];
//		endNode.setIsWall(false);
//		return search(startNode, endNode);
//	}
	
}
